In a graph database, entities are presented as nodes and relationships between those entities are presented as edges in a view of the relational graph maintained by the graph database. The relational graph may be periodically queried by users via graph queries to learn about the relationships between entities. For example, a user may issue a graph query to find friends or contacts within a social network, the documents that a given user has interacted with, the users that a given document has been accessed by, the entities that satisfy various search criteria, etc. The graph query produces a subgraph of the queried graph database that satisfies the query. Further, it is not uncommon for a graph query to start at a node, then follow some set of relationships to a new set of nodes, before again expanding along a new set of relationships to yet another set of nodes. The number of expansion levels is open, and as the complexity of the queries and the size of the graph database increase, the cost of having to span the entire subgraph for every query might become prohibitively large.